:- module(fd_search). :- export nth_value / 3. :- export delete / 5. :- export indomain / 2. :- export delete / 6. :- export search_body / 7. :- export search / 6. :- comment(summary, "This library contains a generic search routine which \nimplements a number of partial search methods (complete, credit, lds, bbs, dbs)"). :- comment(desc, html("This library contains a generic search routine which \nimplements a number of partial search methods (complete, credit, lds, bbs, \ndbs) and some of their combinations.")). :- comment(author, "H. Simonis, J. Schimpf"). :- comment(copyright, "Parc Technologies Ltd/IC-Parc"). :- comment(date, "$Date: 2003/12/08 20:11:29 $"). :- comment(delete / 5, [summary : "Choose a domain variable from a list according to selection criteria.", amode : delete(-, +, -, ++, ++), args : ["X" : " a free variable", "List" : " a list of variables or terms ", "R" : " a free variable ", "Arg" : " an integer", "Select" : " the name of the selection criteria"], desc : html("\nThis predicate chooses one entry in a list of variables or terms based\non some selection criteria. The criteria are explained in detail in\nthe search/6 predicate.

\n"), fail_if : "fails if the list is empty", resat : no, eg : "\n", see_also : [search / 6]]). :- comment(indomain / 2, [summary : "a flexible way to assign values to finite domain variables", amode : indomain(?, ++), args : ["Var" : "a domain variable or an integer", "Method" : "one of the atoms min, max, middle, median, split, interval, random or an integer"], desc : html("This predicate provides a flexible way to assign values to finite \ndomain variables.

\nThe available methods are:\n

min Start the enumeration from the smallest value upwards. \n This behaves like the built-in indomain/1, except that it\n removes previously tested values on backtracking.
max Start the enumeration from the largest value\n downwards.
middle Try the enumeration starting from the middle of the\n domain. On backtracking, this chooses alternatively values above and\n below the middle value, until all alternatives have been tested.
median Try the enumeration starting from the median value\n of the domain. On backtracking, this chooses alternatively values\n above and below the median value, until all alternatives have been\n tested.
split Try the enumeration by splitting the domain\n successively into halves until a ground value is reached. This\n sometimes can detect failure earlier than the normal enumeration\n methods, but enumerates the values in the same order as min.
interval If the domain consists of several intervals, then\n we branch first on the choice of the interval. For one interval, we\n use domain splitting.
random Try the enumeration in a random order. On\n backtracking, the previously tested value is removed. This method\n uses random/1 to create random numbers, use seed/1\n before to make results reproducible.
Value:integer Like middle, but start with the given integer\n Value
sbds_min Like min, but use sbds_try/2 to make choices (for\n use in conjunction with the SBDS symmetry breaking library).
sbds_max Like max, but use sbds_try/2 to make choices (for\n use in conjunction with the SBDS symmetry breaking library).
sbds_middle Like middle, but use sbds_try/2 to make choices\n (for use in conjunction with the SBDS symmetry breaking library).
sbds_median Like median, but use sbds_try/2 to make choices\n (for use in conjunction with the SBDS symmetry breaking library).
sbds_random Like random, but use sbds_try/2 to make choices\n (for use in conjunction with the SBDS symmetry breaking library).
sbds(Value:integer) Like Value:integer, but use sbds_try/2\n to make choices (for use in conjunction with the SBDS symmetry breaking\n library).
gap_sbds_min Like min, but use sbds_try/2 to make choices (for\n use in conjunction with the GAP-based SBDS symmetry breaking library,\n lib(ic_gap_sbds)).
gap_sbds_max Like max, but use sbds_try/2 to make choices (for\n use in conjunction with the GAP-based SBDS symmetry breaking library,\n lib(ic_gap_sbds)).
gap_sbds_middle Like middle, but use sbds_try/2 to make choices\n (for use in conjunction with the GAP-based SBDS symmetry breaking\n library, lib(ic_gap_sbds)).
gap_sbds_median Like median, but use sbds_try/2 to make choices\n (for use in conjunction with the GAP-based SBDS symmetry breaking\n library, lib(ic_gap_sbds)).
gap_sbds_random Like random, but use sbds_try/2 to make choices\n (for use in conjunction with the GAP-based SBDS symmetry breaking\n library, lib(ic_gap_sbds)).
gap_sbds(Value:integer) Like Value:integer, but use sbds_try/2\n to make choices (for use in conjunction with the GAP-based SBDS symmetry\n breaking library, lib(ic_gap_sbds)).
gap_sbdd_min Like min, but use sbdd_try/2 to make choices (for\n use in conjunction with the GAP-based SBDD symmetry breaking library,\n lib(ic_gap_sbdd)).
gap_sbdd_max Like max, but use sbdd_try/2 to make choices (for\n use in conjunction with the GAP-based SBDD symmetry breaking library,\n lib(ic_gap_sbdd)).
gap_sbdd_middle Like middle, but use sbdd_try/2 to make choices\n (for use in conjunction with the GAP-based SBDD symmetry breaking\n library, lib(ic_gap_sbdd)).
gap_sbdd_median Like median, but use sbdd_try/2 to make choices\n (for use in conjunction with the GAP-based SBDD symmetry breaking\n library, lib(ic_gap_sbdd)).
gap_sbdd_random Like random, but use sbdd_try/2 to make choices\n (for use in conjunction with the GAP-based SBDD symmetry breaking\n library, lib(ic_gap_sbdd)).
gap_sbdd(Value:integer) Like Value:integer, but use sbdd_try/2\n to make choices (for use in conjunction with the GAP-based SBDD symmetry\n breaking library, lib(ic_gap_sbdd)).

\nOn backtracking, all methods first remove the previously tested value\nbefore choosing a new one. This sometimes can have a huge impact on\nthe constraint propagation, and normally does not cause much overhead,\neven if no additional propagation occurs.\n"), fail_if : "No", resat : yes, eg : "\ntop:-\n\tX :: 1..10,\n\tindomain(X,min),\n\twrite(X),put(32),\n\tfail.\ntop.\n\n% writes 1 2 3 4 5 6 7 8 9 10\n\ntop:-\n\tX :: 1..10,\n\tindomain(X,max),\n\twrite(X),put(32),\n\tfail.\ntop.\n\n% writes 10 9 8 7 6 5 4 3 2 1\n\ntop:-\n\tX :: 1..10,\n\tindomain(X,middle),\n\twrite(X),put(32),\n\tfail.\ntop.\n\n% writes 5 6 4 7 3 8 2 9 1 10\n\ntop:-\n\tX :: 1..10,\n\tindomain(X,median),\n\twrite(X),put(32),\n\tfail.\ntop.\n\n% writes 5 6 4 7 3 8 2 9 1 10\n\ntop:-\n\tX :: 1..10,\n\tindomain(X,3),\n\twrite(X),put(32),\n\tfail.\ntop.\n\n% writes 3 4 2 5 1 6 7 8 9 10\n\ntop:-\n\tX :: 1..10,\n\tindomain(X,split),\n\twrite(X),put(32),\n\tfail.\ntop.\n\n% writes 1 2 3 4 5 6 7 8 9 10\n\ntop:-\n\tX :: 1..10,\n\tindomain(X,random),\n\twrite(X),put(32),\n\tfail.\ntop.\n\n% writes for example 5 3 7 6 8 1 2 10 9 4\n\n", see_also : [search / 6, indomain / 1, random / 1, seed / 1, sbds_try / 2, sbdd_try / 2]]). :- comment(nth_value / 3, [summary : "return the nth value in a domain", amode : nth_value(+, ++, -), args : ["Domain" : "The domain list to select a value from", "N" : "The position of the value to select", "Value" : "The selected value"], desc : html("Find the nth value in a domain given by an interval or a list of\nintegers and intervals, as it is returned for example by ic's\nget_domain/2 or fd's ::/2.\n"), fail_if : "N < 1 or there are less than N values in the domain.", resat : no, eg : "\n% a typical use\n\n\t....\n\tget_domain(X, L),\n\tnth_value(L, 2, Value),\n\t....\n", see_also : [fd : (::) / 2, ic : get_domain / 2]]). :- comment(search / 6, [summary : "A generic search routine for finite domains or IC which implements \ndifferent partial search methods (complete, credit, lds, bbs, dbs, sbds,\ngap_sbds, gap_sbdd)", amode : search(+, ++, ++, +, ++, +), args : ["L" : "is a list of domain variables (Arg = 0) or a list of\n\t terms (Arg > 0)", "Arg" : "is an integer, which is 0 if the list is a list of\n\t dvarints or greater 0 if the list consists of terms of\n\t arity greater than Arg, the value Arg indicates the\n\t selected argument of the term", "Select" : "is a predefined selection method or the name of a\n\t predicate of arity 2. Predefined methods are input_order,\n\t first_fail, smallest, largest, occurrence,\n\t most_constrained, max_regret, anti_first_fail", "Choice" : "is the name of a predicate of arity 1 or a term\n\t with two arguments with the same functor as a predicate of\n\t arity 3. Some names are already predefined as special\n\t cases and are handled without a meta-call: indomain,\n\t indomain_min, indomain_max, indomain_middle,\n\t indomain_median, indomain_split, indomain_random,\n\t indomain_interval", "Method" : "is one of the following: complete,\n\t bbs(Steps:integer), lds(Disc:integer),\n\t credit(Credit:integer, Extra:integer or bbs(Steps:integer)\n\t or lds(Disc:integer)), dbs(Level:integer, Extra:integer or\n\t bbs(Steps:integer) or lds(Disc:integer)), sbds, gap_sbds,\n\t gap_sbdd", "Option" : "is a list of option terms. Currently recognized\n\t are backtrack(-N), node(++Call), nodes(++N)"], desc : html("Search/6 provides a generic interface to a set of different search\nmethods. It can currently be used with either the finite domains (if\nloaded via lib(fd_search)), or integer IC domains (if loaded via\nlib(ic_search)). By changing the Method argument, different partial\nsearch algorithms (and their parameters) can be selected and\ncontrolled. The search predicate also provides a number of pre-defined\nvariable selection methods (to choose which variable will be assigned next)\nand some pre-defined value assignment methods (to try out the possible\nvalues for the selected variable in some heuristic order), but user-defined\nmethods can be used in their place as well. In order to allow more\nstructure in the application program, it is possible to pass a list of\nterms rather than only a list of domain variables. In this way all\ninformation about some entity can be easily grouped together. It also\nallows more complex labeling methods which combine the assignment of\nmultiple variables (like a preference value and a decision variable).\n\n

\nAll search methods use a stable selection method. If several entries have the \nsame heuristic value, then the first one is selected.\nThe rest of the list is equal to the original list with the selected entry removed,\nthe order of the non-selected entries does not change.\n

\nInteger values are not treated differently from the domain variables,\nthey are selected only if their heuristic value is better than those of the \nother entries.\n

\nThe pre-defined selection methods use the following criteria:\n

input_order the first entry in the list is selected
first_fail the entry with the smallest domain size is selected
anti_first_fail the entry with the largest domain size is selected
smallest the entry with the smallest value in the domain is selected
largest the entry with the largest value in the domain is selected
occurrence the entry with the largest number of attached constraints is selected
most_constrained the entry with the smallest domain size is selected. If several entries have the same domain size, the entry with the largest number of attached constraints is selected.
max_regret the entry with the largest difference between the smallest and second smallest value in the domain is selected. This method is typically used if the variable represents a cost, and we are interested in the choice which could increase overall cost the most if the best possibility is not taken. Unfortunately, the implementation sometimes does not always work. If two decision variables incur the same minimal cost, the regret is not calculated as zero, but as the difference from this minimal value to the next greater value.

\nAny other name is taken as the name of a user-defined predicate of arity 2\nwhich is expected to compute a selection criterion (typically a number), e.g.\n

\nmy_select(X,Criterion) :-\n\t...\t% compute Criterion from variable X\n

\nThe variable-selection will then select the variable with the lowest\nvalue of Criterion. If several variables have the same value, the first\none is selected.\n

\nThe pre-defined choice methods have the following meaning:\n

indomain\nuses the built-in indomain/1. Values are tried in increasing order. \nOn failure, the previously tested value is not removed.
indomain_min\nValues are tried in increasing order. On failure, the previously\ntested value is removed. The values are tested in the same order as\nfor indomain, but backtracking may occur earlier.
indomain_max\nValues are tried in decreasing order. On failure, the previously\ntested value is removed.
indomain_middle\nValues are tried beginning from the middle of the domain. On failure,\nthe previously tested value is removed.
indomain_median\nValues are tried beginning from the median value of the domain. On\nfailure, the previously tested value is removed.
indomain_split\nValues are tried by succesive domain splitting. On failure, the\npreviously tried interval is removed. This enumerates values in the\nsame order as indomain or indomain_min, but may fail earlier.
indomain_random\nValues are tried in a random order. On backtracking, the previously\ntried value is removed. Using this rutine may lead to unreproducable\nresults, as another call wil create random numbers in a different\nsequence. This method uses the built-in random/1 to create\nrandom numbers, seed/1 can be used to force the same number\ngeneration sequence in another run.
indomain_interval\nIf the domain consists of several intervals, we first branch on the\nchoice of the interval. For one interval, we use domain\nsplitting.

\nAny other name is taken as the name of a user-defined predicate of\narity 1, e.g.\n

\nmy_choice(X) :-\n\t...\t% make a choice on variable X\n

\nAlternatively, a term with 2 arguments can be given as the choice-method,\ne.g. my_choice(FirstIn,LastOut). this will lead to the invocation of a\nchoice predicate with arity 3, e.g.\n

\nmy_choice(X,In,Out) :-\n\t...\t% make a choice on variable X, using In-Out\n

\nThis allows user-defined state to be transferred between the subsequent\ninvocations of the choice-predicate (the Out argument of a call to\nmy_choice/3 for one variable is unified with the In argument of the call to\nmy_choice/3 for the next variable, and so on).\n

\nThe different search methods are\n

complete\na complete search routine which explores all alternative choices.
bbs(Steps)\nThe bounded backtracking search allows Steps\nbacktracking steps.
lds(Disc)\nA form of the limited discrepancy search . This method\niteratively tries 0, 1, 2 .. Disc changes against the\nheuristic (first) value. Typical values are between 1 and 3 (which\nalready may create too many alternatives for large problems). The\noriginal LDS paper stated that the discrepancy to be tested first\nshould be at the top of the tree. Our implementation tries the first\ndiscrepancy at the bottom of the tree. This means that solutions may\nbe found in a different order compared to the original algorithm. \nThis change is imposed by the evaluation strategy used and can not be\neasily modified.
credit(Credit, bbs(Steps))\nThe credit based search explores the top of the search tree\ncompletely. Initially, a given number of credits (Credit) are\ngiven. At each choice point, the first alternative gets half of the\navailable credit, the second alternative half of the remaining credit,\nand so on. When the credit run out, the system switches to another\nsearch routine, here bbs. In each of these bounded backtracking\nsearches Steps backtracking steps are allowed before returning\nto the top most part of the tree and choosing the next remaining\ncandidate. A good value for Steps is 5, a value of 0 forces a\ndeterministic search using the heuristic. Typical values for\nCredit are either N or N*N, where N is the number of entries in\nthe list.
credit(Credit, lds(Disc))\nlike the one above, but using lds when the credit runs out. \nTypically, only one (perhaps 2) discrepancies should be allowed.
dbs(Level, bbs(Steps))\nThe depth bounded search explores the first Level\nchoices in the search tree completely, i.e. it tries all values for\nthe first Level selected variables. After that, it switches to\nanother search method, here bbs. In each of these searches,\nSteps backtracking steps are allowed.
dbs(Level, lds(Disc))\nlike the method above, but switches to lds after the first\nLevel variables.
sbds\nA complete search routine which uses the SBDS symmetry breaking library\n(lib(ic_sbds) or lib(fd_sbds)) to exclude symmetric parts of the search tree\nfrom consideration. The symmetry breaking must be initialised through a\ncall to sbds_initialise/4,5 before calling search/6. Currently the only\npre-defined choice methods supported by this search method are\nindomain_min, indomain_max, indomain_middle,\nindomain_median and indomain_random. Any user-defined choice\nmethod used in conjunction with this search method must use sbds_try/2 to\nassign/exclude values or the symmetry breaking will not work correctly.
gap_sbds (Not available for FD.)\nA complete search routine which uses the GAP-based SBDS symmetry breaking\nlibrary lib(ic_gap_sbds) to exclude symmetric parts of the search tree from\nconsideration. The symmetry breaking must be initialised through a call to\nsbds_initialise/5 before calling search/6. Currently the only pre-defined\nchoice methods supported by this search method are indomain_min,\nindomain_max, indomain_middle, indomain_median and\nindomain_random. Any user-defined choice method used in conjunction\nwith this search method must use sbds_try/2 to assign/exclude values or the\nsymmetry breaking will not work correctly.
gap_sbdd (Not available for FD.)\nA complete search routine which uses the GAP-based SBDD symmetry breaking\nlibrary lib(ic_gap_sbdd) to exclude symmetric parts of the search tree from\nconsideration. The symmetry breaking must be initialised through a call to\nsbdd_initialise/5 before calling search/6. Currently the only pre-defined\nchoice methods supported by this search method are indomain_min,\nindomain_max, indomain_middle, indomain_median and\nindomain_random. Any user-defined choice method used in conjunction\nwith this search method must use sbdd_try/2 to assign/exclude values or the\nsymmetry breaking will not work correctly.

\nThe option list is used to pass additional parameters to and from the\nprocedure. The currently recognized options are:\n

backtrack(-N)\nreturns the number of backtracking steps used in the search\nroutine
nodes(++N)\nsets an upper limit on the number of nodes explored in the search. If\nthe given limit is exceeded, the search routine stops the exploration\nof the search tree.
node(daVinci)\ncreate a drawing of the search tree using the daVinci grapg drawing\ntool. Each node of the search tree is shown as a node in the tree. \nThe label of the node is the selected term of the list.
node(daVinci(++Call))\nas the previous option, it creates a drawing of the search tree using\nthe daVinci graph drawing tool. But instead of using the complete\nselected term as the label, it call the predicate Call/2 to\nchoose which part of the selected term to display.

\n"), fail_if : "Fails if the search tree generated does not contain any solution. \nFor partial search methods, this does not mean that the problem does not \nhave a solution, but only that the part of the tree generated did not \ncontain one.", resat : yes, eg : "\ntop:-\n\tlength(L,8),\n\tL :: 1..8,\n\tsearch(L,0,input_order,indomain,complete,[]).\n\ntop:-\n\tlength(L,8),\n\tL :: 1..8,\n\tsearch(L,0,input_order,indomain,bbs(15),[]).\n\ntop:-\n\tlength(L,8),\n\tL :: 1..8,\n\tsearch(L,0,input_order,indomain,lds(2),[]).\n\ntop:-\n\tlength(L,8),\n\tL :: 1..8,\n\tsearch(L,0,input_order,indomain,credit(64,bbs(5)),[]).\n\ntop:-\n\tlength(L,8),\n\tL :: 1..8,\n\tsearch(L,0,input_order,indomain,dbs(2,lds(1)),[]).\n\n% a more complex example with different methods and heuristics\n% the list to be assigned is a list of terms queen/2\n\n:- local struct(queen(place,var)).\n\ntop:-\n\tmember(Method,[complete,lds(2),credit(64,5),bbs(1000),dbs(5,10)]),\n\tmember(Select,[first_fail,most_constrained,input_order]),\n\tmember(Choice,[indomain,\n\t indomain_min,\n\t\t indomain_max,\n\t\t indomain_middle,\n\t\t indomain_median,\n\t\t indomain_split,\n\t\t indomain_random]),\n\twriteln(queen(Method,Select,Choice)),\n\tonce(queen_credit(64,Select,Choice,Method,L,Back)),\n\twriteln(L),\n\twriteln(backtrack(Back)),\n\tfail.\ntop:-\n\tnl.\n\nqueen_credit(N,Select,Choice,Method,L,Back):-\n\tcreate_queens(1,N,Queens,L),\n\tsetup(L),\n\trearrange(Queens,Queens,[],[],Queens1),\n\tsearch(Queens1, var of queen, Select, Choice, Method, [backtrack(Back)]).\n\nrearrange([],Last,Last,Res,Res).\nrearrange([_],[Mid|Last],Last,Res,[Mid|Res]).\nrearrange([_,_|S],[H|T],A1,In,Res):-\n\trearrange(S,T,[A|A1],[H,A|In],Res).\n\ncreate_queens(N,M,[],[]):-\n\tN > M,\n\t!.\ncreate_queens(N,M,[queen{place:N,var:X}|T],[X|L]):-\n\tX :: 1..M,\n\tN1 is N+1,\n\tcreate_queens(N1,M,T,L).\n\nsetup([]).\nsetup([H|T]):-\n\tsetup1(H,T,1),\n\tsetup(T).\n\nsetup1(_,[],_).\nsetup1(X,[Y|R],N):-\n\tX #\\= Y,\n\tX #\\= Y + N,\n\tY #\\= X + N,\n\tN1 is N+1,\n\tsetup1(X,R,N1).\n\n\n% this example shows how to pass information from one assignment step \n% to the next\n% this uses a term of two arguments as the choice argument\n% The example also shows the use of the option argument:\n% the search tree generated is drawn with the daVinci graph drawing tool\n% and the search is limited to 1000 nodes.\n% The number of backtracking steps is returned in the variables Back.\n:-local struct(country(name,color)).\n\ntop:-\n\tcountries(C),\n\tcreate_countries(C,Countries,Vars),\n\tfindall(n(A,B),n(A,B),L),\n\tsetup(L,Countries),\n\tsearch(Countries,\n\t color of country, % select based on this variable\n\t most_constrained,\n\t assign([1,2,3,4],Out), % this calls assign/3\n\t complete,\n\t [backtrack(Back),node(daVinci),nodes(1000)]),\n\twriteln(Vars),\n\twriteln(Back),\n\twriteln(Out).\n\ncreate_countries([],[],[]).\ncreate_countries([C|C1],[country{name:C, color:V}|R1],[V|V1]):-\n\tV :: 1..4,\n\tcreate_countries(C1,R1,V1).\n\nsetup([],_L).\nsetup([n(A,B)|N1],L):-\n\tmember(country{name:A, color:Av},L),\n\tmember(country{name:B, color:Bv},L),\n\tAv #\\= Bv,\n\tsetup(N1,L).\n\n% this is the choice predicate\n% the first argument is the complete selected term\n% the second is the input argument\n% the third is the output argument\n% here we pass a list of values and rotate this list from one step to the next\nassign(country{color:X},L,L1):-\n\trotate(L,L1),\n\tmember(X,L).\n\nrotate([A,B,C,D],[B,C,D,A]).\n\n% another example of argument passing \n% here each entry gets the same information\n% it is passed unchanged from one level to the next\n\ntop:-\n\t...\n\tlength(L,N),\n\tL :: 1..10,\n\t...\n search(L,\n\t 0,\n\t most_constrained,\n\t % pass two lists as the In argument of assign\n\t % try the odd numbers before the even numbers\n\t assign([1,3,5,7,9]-[2,4,6,8,10],_), \n\t complete,[]),\n\t...\n\n% this is the assignment routine\n% the first argument is a \n% Pass the In argument as the Out argument\n% try values from list L1 before values from list L2\nassign(X,L1-L2,L1-L2):-\n\tmember(X,L1);member(X,L2).\n\n% and another example from square placement\n% alternatively try minimal and maximal values first\n\n:-local struct(square(x,y,size)).\n\ntop:-\n\tdata(L),\n\tcreate_squares(L,Squares),\n\t...\n search(Squares,\n\t 0, % this value does not matter if input_order is chosen\n\t input_order,\n\t assign(min,_),\n\t complete,\n\t []),\n\t...\n\n% the assignment routine\n% alternate between min and max for consecutive levels in the search\nassign(square{x:X,y:Y},Type,Type1):-\n\tswap(Type,Type1),\n\tindomain(X,Type),\n\tindomain(Y,Type).\n\nswap(max,min).\nswap(min,max).\n\n% this example shows that the choice routine may consist of several clauses\n% the idea comes from a graph coloring heuristic\n\ntop:-\n\tlength(L,N),\n\tL :: 1..100,\n\t...\n search(L,\n\t 0,\n\t most_constrained,\n\t assign(0,K), The In argument is the highest color used so far\n\t complete,[]),\n\t...\n\n\n% assign variable X either to one of the colors 1..K \n% which have already been used, or to the new color K+1\n% we do not need to try other values K+2 etc, as this is a symmetry that\n% we can avoid\nassign(X,K,K):-\n\tX #=< K,\n\tindomain(X).\nassign(K1,K,K1):-\n\tK1 is K+1.\n\n\n% example showing use of the SBDS library with a user-defined choice method\n% which calls sbds_try/2.\n\ntop:-\n\tdim(M, [8]),\n\tM[1..8] :: 1..8,\n\t...\n\tsbds_initialise(M,SymPreds,#=,[]),\n\tM =.. [_|L],\t% get list of variables for search routine\n\tsearch(L,0,first_fail,sbds_indomain_max,sbds,[]).\n\nsbds_indomain_max(X):-\n\tnonvar(X).\nsbds_indomain_max(X):-\n\tvar(X),\n\tget_max(X,Max),\n\tsbds_try(X,Max),\n\tsbds_indomain_max(X).\n\n\n% Example showing use of the GAP-based SBDS library with a user-defined\n% choice method which calls sbds_try/2. (For the GAP-based SBDD library,\n% just substitute \"sbdd\" for each occurrence of \"sbds\" below.)\n\ntop:-\n\tdim(M, [8]),\n\tM[1..8] :: 1..8,\n\tsbds_initialise(M,[vars],values:1..8,[symmetry(s_n,[vars])],[]),\n\tM =.. [_|L],\t% get list of variables for search routine\n\tsearch(L,0,first_fail,gap_sbds_indomain_max,gap_sbds,[]).\n\ngap_sbds_indomain_max(X):-\n\tnonvar(X).\ngap_sbds_indomain_max(X):-\n\tvar(X),\n\tget_max(X,Max),\n\tsbds_try(X,Max),\n\tgap_sbds_indomain_max(X).\n", see_also : [indomain / 1, indomain / 2, labeling / 1, deleteff / 3, deleteffc / 3, sbds_initialise / 4, sbds_initialise / 5, sbds_try / 2, sbdd_initialise / 5, sbdd_try / 2, library(ic_sbds), library(fd_sbds), library(ic_gap_sbds), library(ic_gap_sbdd)]]). :- comment(delete / 6, hidden). :- comment(search_body / 7, hidden).